1. Field of the Invention
The present invention relates to wireless communication devices organized as ad-hoc multihopping networks and, more particularly, to ad-hoc multihopping wireless networks that plan network transmissions in a Time Division Multiple Access (TDMA) manner.
2. Description of the Related Art
Wireless communication networks, such as mobile wireless telephone networks, have become increasingly prevalent over the past decade. These wireless communications networks are commonly referred to as “cellular networks”, because the network infrastructure is arranged to divide the service area into a plurality of regions called “cells”, as depicted in FIG. 1.
In recent years, the concept of meshed wireless networks has been developed. According with this concept, each node of the network has the capability to receive and transmit radio signals carrying digital information. From one perspective, it is similar with land networks where a multitude of nodes creates a mesh through which data packets are routed from source to destination. As can be appreciated by one skilled in the art, network nodes transmit and receive data packet communications in a multiplexed format, such as time-division multiple access (TDMA) format, code-division multiple access (CDMA) format, or frequency-division multiple access (FDMA) format, which enables a single transceiver at a first node to communicate simultaneously with several other nodes in its coverage area.
A wireless device operating in an ad-hoc multi-hopping network has three main components: the transceiver, a CPU, and a memory component, as depicted in FIGS. 2 and 3. The transceiver is a complex radio receiver/transmitter that receives and transmits signals from and to other devices in the network. The memory component holds instructions and data that the CPU uses for controlling the transceiver operations and for storing data to be transmitted or data that has been received. Depending on the functionality that the wireless device provides, it can be connected to a host, which in turn, could be connected to any network. For example, a mobile telephone is a wireless device, for which the host functionality is provided by a sound encoder and decoder. Moreover, handheld, laptop, and desktop computers can be hosts of wireless communication devices, which, in turn, provide those computers with wireless networking capabilities.
Many differences exist between land and wireless mesh networks. For example, in wireless networks, a radio transmission is received by all neighbors located within the propagation range and almost all nodes of the wireless networks are mobile. In wired land networks, all routes can be computed and stored in databases when the wires between nodes are installed. In wireless ad-hoc networks instead, the routes between two nodes that need to communicate have to be computed at utilization time (on demand) and maintained during the connection, due to the fact that any node along the link route can move out of the radio propagation range of neighbors, thus breaking the connection.
Because of the requirement to build network relations when they are needed, meshed wireless networks are called “ad-hoc networks.” They are also called “multi-hopping” because the information, which is presented in packets of data, travels from source to destination in a “hopping” manner from one node to another along the route. Because of the capability of repairing broken routes, those networks are said to be “self healing”. FIG. 4 illustrates an example ad-hoc network, in which devices 106-1-106-n provide a wireless network with the connection to the world of communications. Because these devices use land interfaces, they are required to remain fixed. All other devices, however, can move in any direction as long as a path between devices soliciting communication can be built.
Several other differences exist between ad-hoc multi-hopping networks and cellular networks. In particular, for example, the mobility of ad-hoc networks requires that almost all nodes operate on batteries. Moreover, because each node has to support not only its own communication, but the communications between neighbors as well, ad-hoc devices have to transmit signals for longer intervals than regular cellular telephones. Therefore, to ensure that the device does not drain the battery too fast, the transmitting power of ad-hoc devices has to be much smaller than the transmitting power of regular cell phones. For this reason, the ad-hoc devices can communicate regularly at distances smaller than 1 km, compared with 10-15 km maximum range of cellular devices.
Important differences between ad-hoc multi-hopping networks and cellular networks are also derived from the fact that ad-hoc networks are “horizontal” with no hierarchical structure, while the cellular networks use the base stations as “the master” of the cell network. A first difference derived from the horizontality of the network relations is the fact that all devices operating in ad-hoc networks should use the same radio frequency in order to communicate one with another. A second difference is the fact that ad-hoc networks have to use distributed algorithms for managing the common resources, in opposition with cellular networks where the base station is responsible for collecting data about network activity and performing the management of resources.
More sophisticated ad-hoc networks are also being developed which, in addition to enabling mobile nodes to communicate with each other as in a conventional ad-hoc network, further enable the mobile nodes to access a fixed network such as those on the public switched telephone network (PSTN), and the Internet. Details of these advanced types of ad-hoc networks are described in U.S. patent application Ser. No. 09/897,790 entitled “Ad Hoc Peer-to-Peer Mobile Radio Access System Interfaced to the PSTN and Cellular Networks”, filed on Jun. 29, 2001, in U.S. Pat. No. 6,807,165, entitled “Time Division Protocol for an Ad-Hoc, Peer-to-Peer Radio Network Having Coordinating Channel Access to Shared Parallel Data Channels with Separate Reservation Channel”, and in U.S. patent application Ser. No. 09/815,164 entitled “Prioritized-Routing for an Ad-Hoc, Peer-to-Peer, Mobile Radio Access System”, filed on Mar. 22, 2001, the entire content of each being incorporated herein by reference.
For some networks, where the throughput is not crucial to performance (such as, for example, in industrial telemetering), rough synchronization within the network can be satisfactory. Such rough synchronizations, however, fail to satisfy the requirements for supporting high throughput (e.g., hundreds of mega bits per second) for interactive voice and video communications or for file transfer. True high-precision synchronization, in this regard, has been identified for some time as being unachievable in ad-hoc networks. In fact, similar synchronization problems are encountered in radio networks using frequency hopping. In such networks, the receiver and transmitter change the transmitting and the receiving frequencies at the same moment, in order to ensure a continuous communication. Although, in this case the synchronization is required between two nodes only, the complexity of the problem is identified in U.S. Patent Application Ser. No. 20040198363, entitled “Wireless Device And Method Using Frequency Hopping And Sweep Modes”, filed on Jan. 13, 2003, which presents a method for using frequency hopping without synchronization between a receiver and a transmitter.
Many references relate to the synchronization of devices in hierarchical wireless networks, where one or several synchronized masters operate as timeservers. U.S. Patent Application Serial No. 20040190487, entitled “Method For Synchronizing A Control Channel To A Working Channel”, filed on Mar. 31, 2003, for example, relates to a method for synchronizing a control channel to a working channel, wherein the synchronization is “at bit level” which ensures a precision of about 7.5 ms. Moreover, U.S. Pat. No. 6,792,247 relates to a method for synchronizing reception in wireless networks, in which a “synchronization packet” of a special format is transmitted before a data packet is transmitted. U.S. Pat. Nos. 6,785,253 and 6,622,022 also disclose methods for synchronizing hierarchical wireless networks wherein at least one node is selected as the “central transfer node” or as the “main network node” which is responsible for providing frame synchronization services. Moreover, U.S. Pat. No. 6,546,026 relates to a method for improving the time synchronization in wireless applications (e.g., TDMA), which is applicable to base stations using an array of antennae for receiving and decoding signals from several sources simultaneously.
Methods for synchronizing cellular wireless networks using GPS timing signals can also be found in U.S. Pat. Nos. 6,542,754 and 6,538,600. Moreover, U.S. Pat. No. 6,466,608 relates to a synchronization method that requires defining a hierarchical structure of the network, wherein the synchronization process is controlled by assigned “master nodes.” Moreover, a method for synchronizing the operation of end nodes in wireless LAN is presented in U.S. Pat. No. 6,069,887. Moreover, a method for correcting the ATM network synchronization with the round trip duration (similar with propagation time) is presented in U.S. Pat. Nos. 6,438,702. 5,923,902 relates to a method similar to those of the '702 patent, but wherein “round trip” is replaced by “time lag.” Moreover, a similar method applicable to wireless LAN using frequency hopping is described in U.S. Pat. No. 5,408,506, wherein all messages have a field that contains the time when the message was transmitted. Moreover, U.S. Pat. No. 5,812,547 relates to a method for transmitting data packets in a wireless network, without dependence on fixed time slot or a central timing mechanism.
Methods for scheduling time slots and mini timeslots for supporting voice, video and data transmissions over a cellular communication network (e.g., GSM), are presented in U.S. Pat. Nos. 6,438,136 and 6,618,363. Moreover, U.S. Pat. No. 6,594,273 relates to a method for communicating in an ad-hoc multihopping network, wherein the network comprises active and passive terminals, and wherein only the active terminals participate in routing and synchronization. U.S. Pat. Nos. 6,807,165 and 5,699,388 present methods using a unique time source and propagating the synchronization in the network from upstream to downstream terminals. Moreover, U.S. Patent Application Serial No. 20040005902, entitled “System and method for correcting the clock drift and maintaining the synchronization of low quality clocks in wireless networks”, filed Jul. 5, 2002, relates to a method that allows synchronization of terminals at any precision, using a “reference clock” that operates as a network master. All of the documents cited above are incorporated by reference herein.